#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    vector<string> ret;

    bool judge(string& str){
        int status = 0;
        for(char c : str){
            if(c == '('){
                status++;
            }else{
                status--;
            }
            if(status < 0){
                return false;
            }
        }
        return status == 0;
    }
    //递归
    void dfs(int n, string str){
        if(n*2 == str.size()){
            if(judge(str)){
                ret.push_back(str);
            }
            return;
        }

        str = str + "(";
        dfs(n, str);
        str.pop_back();
        str = str + ")";
        dfs(n, str);
        str.pop_back();
    }

    void back(int n, int status, string str){
        if(str.size() == n*2){
            if(status == 0){
                ret.push_back(str);
            }
            return;
        }

        str = str + "(";
        status++;
        back(n, status, str);
        str.pop_back();
        status--;
        str = str + ")";
        status--;
        if(status < 0){
            return;
        }
        back(n, status, str);
        str.pop_back();

    }

    public:
    vector<string> ans1(int n){
        dfs(n, "");

        return ret;
    }

    vector<string> ans2(int n){
        int status = 0;
        back(n, status, "");

        return ret;
    }
};

void test(){
    Solution s;
    int n = 3;

    // vector<string> ret = s.ans1(n);
    vector<string> ret = s.ans2(n);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i] << endl;
    }
}

int main(void){
    test();

    return 0;
}